#include<stdio.h>

#define N 8  //迷宫大小

int maze[N][N] = {{0, 0, 0, 0, 0, 0, 0, 0}, //迷宫
                  {0, 1, 1, 1, 1, 0, 1, 0},
                  {0, 0, 0, 0, 1, 0, 1, 0},
                  {0, 1, 0, 0, 0, 0, 1, 0},
                  {0, 1, 0, 1, 1, 0, 1, 0},
                  {0, 1, 0, 0, 0, 0, 1, 1},
                  {0, 1, 0, 0, 1, 0, 0, 0},
                  {0, 1, 1, 1, 1, 1, 1, 0}};

int fx[4] = {1, 0, -1, 0},
        fy[4] = {0, 1, 0, 1}; //用来表示该点四个方向的下一个点

struct {    //队列存储结构
    int x;
    int y;
    int pre;
} sq[N * N];

int dist[N][N];    //存储距离

struct {    //存储解坐标
    int x;
    int y;
} Node[N * N];


int qh, qe; //表示队列头尾

int check(int i, int j) {
    int flag = 1;
    if (i < 0 || i > 7 || j < 0 || j > 7)    //判断越界
        flag = 0;
    if (maze[i][j] == 1 || maze[i][j] == -1)    //maze[i][j]=1，该点不通，为0可通，为-1已经访问过
        flag = 0;
    return flag;
}

void output() { //输出可通路的x、y坐标 |从起始点输出通路坐标
    //printf("(%d,%d) ", sq[qe].x, sq[qe].y);
    int i = 1,j;
//    Node[0].x = sq[qe].x;
//    Node[0].y = sq[qe].y;
//    while (sq[qe].pre >= 0) {
//        qe = sq[qe].pre;
//        Node[i].x = sq[qe].x;
//        Node[i++].y = sq[qe].y;
        //printf("(%d,%d) ", sq[qe].x, sq[qe].y);
//    }
//    while ((i = i - 1) >= 0) {
//        printf("(%d,%d) ", Node[i].x, Node[i].y);
//    }
    for (i = 0; i <N ; ++i) {    //输出可通路每个坐标到起始点的距离
        for (j = 0; j <N ; ++j) {
            if (dist[i][j]==-1)
            {
                printf("   ");
                continue;
            }
            printf("%3d",dist[i][j]);
        }
        printf("\n");
    }
}

int search() {
    int i, j, k;
    qh = -1;
    qe = 0;
    maze[0][0] = -1;   //表示已经访问了
    sq[0].pre = -1;     //起始节点入队
    sq[0].x = 0;
    sq[0].y = 0;
    dist[0][0] = 0;
    while (qh != qe) {
        qh = qh + 1;
        for (k = 0; k < 4; k = k + 1) { //寻找该点四个方向可通的点
            i = sq[qh].x + fx[k];    //四个方向的x坐标
            j = sq[qh].y + fy[k];    //四个方向的y坐标
            if (check(i, j) == 1) {    //判断是否可通
                qe = qe + 1;
                sq[qe].x = i; //路可通，入队
                sq[qe].y = j;
                sq[qe].pre = qh; //前一个点在队列中的下标
                maze[i][j] = -1; //该点访问过，设置为-1
                dist[i][j] = dist[sq[qh].x][sq[qh].y] + 1;    //距离加1
                if (sq[qe].x == 7 && sq[qe].y == 7) {
                    return 1;    //有解返回1
                }
            }
        }
    }
    return 0;    //无解返回0
}

int main() {
    int i, j;
    for (i = 0; i < N; ++i) {
        for (j = 0; j < N; ++j) {
            dist[i][j] = -1;
        }
    }
    if (search()) //判断解
    {
        output();    //输出结果
    } else {
        printf("No solution.\n");
    }
}
